package main

func mergeSort(nums []int) {
	if len(nums) < 2 {
		return
	}
	mid := len(nums) / 2
	mergeSort(nums[0:mid])
	mergeSort(nums[mid:])
	merge(nums, mid)
}

// pivot is the first index of right slice
func merge(nums []int, pivot int) {
	var result []int
	i := 0
	j := pivot
	for i < pivot && j < len(nums) {
		if nums[i] < nums[j] {
			result = append(result, nums[i])
			i++
		} else {
			result = append(result, nums[j])
			j++
		}
	}
	if i < pivot {
		result = append(result, nums[i:pivot]...)
	}
	if j < len(nums) {
		result = append(result, nums[j:len(nums)]...)
	}
	copy(nums, result)
}

func main() {
	nums := []int{1, 3, 5, 2, 4, 6, 8}
	mergeSort(nums)
	println(nums)
}
